/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 针对所有的二叉树的广度搜索
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function (root, val) {
    let queue = [root];
    while (queue.length) {
        let len = queue.length, node;
        for (let i = 0; i < len; i++) {
            node = queue.shift()
            if (node.val === val) {
                return node
            }
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
    }
    return null
};



/**
 * 针对所有二叉树的深度递归
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function (root, val) {
    return searchLevel(root, val) || null
};

function searchLevel(root, val) {
    if (root.val === val) {
        return root
    }


    if (root.left !== null) {
        let node = searchLevel(root.left, val)
        if(node) return node
    }
    if (root.right !== null) {
        let node = searchLevel(root.right, val)
        if(node) return node
    }
}

/**
 * 针对搜索二叉树的搜索递归（搜索二叉树的父节点比左子节点大，比右子节点小）
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function (root, val) {
    return searchLevel(root, val) || null
};

function searchLevel(root, val) {
    if (root === null) {
        return null
    }
    if (root.val === val) {
        return root
    }

    return searchLevel(root.val > val ? root.left : root.right, val)
}

/**
 * 针对搜索二叉树的搜索迭代遍历
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function (root, val) {
    let queue = [root];
    while (queue.length) {
        let len = queue.length, node;
        for (let i = 0; i < len; i++) {
            node = queue.shift()
            if (node.val === val) {
                return node
            } else if (node.val > val) {
                node.left && queue.push(node.left)
            } else {
                node.right && queue.push(node.right)
            }
        }
    }
    return null
};

/**
 * 迭代官解
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function (root, val) {
    while (root) {
        if (root.val === val) {
            return root
        } else if (root.val > val) {
            root = root.left
        } else {
            root = root.right
        }
    }
    return null
};